package com.heap;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

class Point {
    int x;
    int y;

    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "[" + this.x + "," + this.y + "]";
    }
}

public class KClosest {

    public static int[][] kClosest(int[][] points, int k) {
        int[][] result = new int[k][2];
        if (points == null || points.length == 0) return result;

        PriorityQueue<int[]> minHeap = new PriorityQueue<>(k, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return (o1[0] * o1[0] + o1[1] * o1[1]) - (o2[0] * o2[0] + o2[1] * o2[1]);
            }
        });

        for (int i = 0; i < points.length; i++) {
            minHeap.add(points[i]);
        }

        for (int i = 0; i < k; i++) {
            result[i] = minHeap.poll();
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] points = {{1, 3}, {-2, 2}};
        int k = 1;
        System.out.println(Arrays.toString(kClosest(points,k)));

        /*Point[] points = new Point[5];
        Point p1 = new Point(4, 6);
        Point p2 = new Point(4, 7);
        Point p3 = new Point(4, 4);
        Point p4 = new Point(2, 5);
        Point p5 = new Point(1, 1);
        Point origin = new Point(0, 0);
        points[0] = p1;
        points[1] = p2;
        points[2] = p3;
        points[3] = p4;
        points[4] = p5;

        Point[] result = kClosest(points, origin, 3);
        System.out.println(Arrays.toString(result));*/
    }

    private static Point global_origin = null;

    public static Point[] kClosest(Point[] points, Point origin, int k) {
        global_origin = origin;
        PriorityQueue<Point> minHeap = new PriorityQueue<>(k, new Comparator<Point>() {
            @Override
            public int compare(Point p1, Point p2) {
                int diff = getDistance(p2, global_origin) - getDistance(p1, global_origin);
                if (diff == 0) {
                    diff = p2.x - p1.x;
                }
                if (diff == 0) {
                    diff = p2.y - p1.y;
                }
                return diff;
            }

            private int getDistance(Point p1, Point p2) {
                return 0;
            }
        });

        for (int i = 0; i < points.length; i++) {
            minHeap.offer(points[i]);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        k = minHeap.size();
        Point[] result = new Point[k];
        while (!minHeap.isEmpty()) {
            result[--k] = minHeap.poll();
        }
        return result;
    }
}
